package top.interview.string

import problem.Problem

import scala.collection.mutable

class Q131PalindromePartitioning extends Problem {

  def partition(s: String): List[List[String]] = {
    // 存储回文序列的右编号
    val a = (0 until s.length).map(mutable.Buffer[Int](_))
    for {
      i <- 0 until s.length - 1
      j <- i + 1 until s.length if isPalindrome(s, i, j)
    } a(i) += j

    //    println(a)
    partition(s, a, 0)
  }

  def isPalindrome(s: String, l: Int, r: Int): Boolean = {
    val rs =
      if (l == r) true
      else !(0 to (r + 1 - l) / 2).exists(i => s(l + i) != s(r - i))
    //    if (rs) println(s"${s.substring(l, r + 1)} is palindrome")
    rs
  }

  def partition(s: String, a: Seq[mutable.Buffer[Int]], l: Int): List[List[String]] = {
    if (l >= a.length) List(Nil)
    else for {
      r <- a(l).toList
      part <- partition(s, a, r + 1)
    } yield s.substring(l, r + 1) :: part
  }

  override def test(): Unit = {
    println(partition("abbab"))
  }
}
